perm filename MEMORY[0,BGB]2 blob
sn#071773 filedate 1973-11-14 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 4.0 MEMORY - DATA STRUCTURES.
C00003 00003 4.1 Introduction to Geometric Data Structures.
C00005 00004 4.2 The Winged Edge Polyhedron Representation.
C00007 00005 FEV Sequential Accessing.
C00011 00006 Figure - THE WINGED EDGE.
C00012 00007 Winged Edge Data Structure.
C00017 00008 4.3 Representation of a Geometric Mental Universe.
C00019 00009
C00020 00010 4.5 Interfacing to Other Data Types.
C00021 ENDMK
C⊗;
4.0 MEMORY - DATA STRUCTURES.
4.1 Introduction to Geometric Data Structures.
4.2 The Winged Edge Polyhedron Representation.
4.3 Representation of a Geometric Mental Universe.
4.4 The CRE and the FEV Image Representations.
4.5 Interfacing to Other Data Types.
4.1 Introduction to Geometric Data Structures.
In order to get a computer to deal with the physical world
it must have a data representation on which computations involving
space, time, shape, size and the appearance of things can be done.
In this section, a representation for the topology, geometry and
photometry of everyday things is explained. The data structures
discussed are implemented as small blocks of words containing
pointers and data in the fashion usual to graphics and simulation;
an introduction to this technology can be found in Knuth; and
although the language of implementation is PDP-10 machine code, the
data and functions presented below are accessible from higher level
languages like LISP and ALGOL.
4.2 The Winged Edge Polyhedron Representation.
Figure 1.6
FACE PERIMETER - a face is surrounded by edges and vertices.
VERTEX
⊗
/ \
/ \
/ \
/ \
EDGE / \ EDGE
/ \
/ FACE \
/ \
/ \
/ \
VERTEX ⊗---------------------⊗ VERTEX
EDGE
Figure 1.7
VERTEX PERIMETER - a vertex is surrounded by edges and faces.
EDGE
|
|
FACE | FACE
|
⊗ VERTEX
/ \
/ \
/ \
/ \
/ FACE \
EDGE EDGE
Figure 1.8
EDGE PERIMETER - an edge is surrounded by 2 faces & 2 vertices.
VERTEX
⊗
|
|
FACE E FACE
|
|
⊗
VERTEX
FEV Sequential Accessing.
FEV Perimeter Accessing.
Within each body there is face, edge and vertex sequential
accessing. Given a body, all its faces, or edges, or vertices need to
be readily available since perspective projection loops thru all the
vertices, and the process of display clipping loops thru all the
edges, and the act of checking for body intersection loops thru all
the faces.
In LISP, one might provide FEV sequential accessing by
placing a list of faces, a list of edges and a list of vertices on
the property list of each body, so that a cube might be represented
as:
(DEFPROP CUBE (F1 F2 F3 F4 F5 F6) FACES)
(DEFPROP CUBE (E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12)EDGES)
(DEFPROP CUBE (V1 V2 V3 V4 V5 V6 V7 V8) VERTICES)
Among the faces, edges and vertices of a body there
is perimeter accessing. Faces have a perimeter of edges and vertices
[figure 1.6]; less commonly used, vertices have a perimeter of edges
and faces [figure 1.7]; and of particular note, edges have a
perimeter always formed by two faces and two vertices, [figure 1.8].
Perimeter accessing requires that given a face, edge or vertex, that
the perimeter of that entity be readily accessible. Since the surface
of a polyhedron is orientable, that is has a well defined inside and
outside, (Klein bottles with their crosscaps will not be modeled),
such perimeter lists can be ordered (say clockwise) with respect to
the exterior of the polyhedron. Perimeter accessing is mentioned in
Guzman [reference 6] and Falk [reference 4] and is the underlying
basis of part-II of this paper which presents a polyhedron model
built for accessing and altering face, edge and vertex perimeters.
Figure - THE WINGED EDGE.
(As viewed from the exterior of a solid).
\ /
NCCW(E) \ / PCW(E)
\ /
\ /
\ /
⊗ PVT(E)
|
|
NFACE(E) E PFACE(E)
|
|
NVT(E) ⊗
/ \
/ \
/ \
NCW(E) / \ PCCW(E)
/ \
Winged Edge Data Structure.
Bodies, faces, edges and vertices are represented by blocks
of contiguously addressed words. A single block size of ten words is
adequate. A single word, like a LISP node, can hold two addresses or
a floating point number. The BFEV blocks are pointed at by the
address of their word numbered zero which contains control bits
indicating whether the block is a body, face, edge or vertex. Figure
2.1 illustrates the block format that is being presented as an
example of a winged edge data structure; a minimal number of words
for each block is indicated.
The basic geometric datum is the vertex locus, which is
stored in three words of each vertex block at positions -3, -2, -1;
these positions are named XWC, YWC, ZWC respectively; the letters
"WC" standing for "world coordinates".
The basic topological data are the three rings of the body;
(a ring of faces, a ring of edges, and a ring of vertices) and the
winged edge pointers (eight such pointers in each edge block,and one
such pointer in each face and vertex block). The face, edge and
vertex ring pointers are stored at positions +1, +2, +3; each
position has two names: NFACE, NED, NVT for the left pointers
respectively; and PFACE, PED, PVT for the right. A face, edge or
vertex can only belong to one body and so there is only one body node
in a given face, edge or vertex ring; and that body node serves as
the head of the ring. The reason for double pointer rings is for the
sake of rapid deletion; other minor advantages would not justify the
use of double rings.
The eight WINGED pointers of an edge block include: two
pointers to the faces of that edge, two pointers to the vertices of
that edge, and four pointers to the next edges clockwise and counter
clockwise in each of that edge's two faces; these last four pointers
are called the wings of that edge. As figure 2.2 suggests, four of
these eight pointers are stored in the same positions and referred to
by the same names as the face and vertex ring pointers; namely the
NFACE, PFACE, NVT and PVT pointers. There are four ways in which a
pair of faces and a pair of vertices can be placed into the two face
positions and two vertex positions of an edge; by constraining these
choices two bits are implicitly encoded, one bit is called the edge
parity, and the other is called the surface parity; these bits are
explained later. Finally, the single winged edge pointer found in
faces and vertices is kept in the position named PED and it points to
one of the edges belonging to that face or vertex.
Although the vertices in figure 2.2 are shown with three
edges, vertices may have any number of edges; those other potential
edges would not be directly connected to E and so were not shown.
4.3 Representation of a Geometric Mental Universe.
At the top of the data structure is a single universe node
from which everything else can be reached. Immediately below the
universe node is a ring of world models. A robot dealing with
physical world sensor input, such as video data, has one of its world
models dedicated to simulating the immediate here and now; this
mental world is called the reality world model. In addition to the
reality world, a robot may have fantasy world models for problem
solving, planning or for recalling platonic object prototypes. In the
following, a two world mental universe will be the most common, with
the reality world being referred to as a "map" and the fantasy world
being referred to as a "dictionary".
Geometric world models have four basic kinds of nodes:
body, face, edge and vertex. The face, edge and vertex nodes are used
to form polyhedrons which may be attached to body nodes. Body nodes
in turn are connected to each other in rings and trees to form a
world model. Additional kinds of nodes discribe cameras and light
sources as well as temporary data such as shadows, spines, and
trajectories.
The image data structure presented in this section is a
computer's internal notation for what is vulgarly called a line
drawing; the common term is misleading because it does not suggest
the equally important space between the lines; terms closer to the
idea would be "mosaic drawing" or "stained glass window drawing".
The data structure has main levels: TV raster, video
intensity contour, arc contour, and region-edge.
4.5 Interfacing to Other Data Types.